package com.moyoutian.leetcode;

/**
 * 67. 二进制求和
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 * <p>
 * 输入为 非空 字符串且只包含数字 1 和 0。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * <p>
 * 示例 2:
 * <p>
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * 每个字符串仅由字符 '0' 或 '1' 组成。
 * 1 <= a.length, b.length <= 10^4
 * 字符串如果不是 "0" ，就都不含前导零。
 */
public class Demo67 {

    public static void main(String[] args) {
        String a = "10", b = "11";
        System.out.println(addBinary(a, b));
    }

    public static String addBinary(String a, String b) {
        if (a == null || a.length() == 0 || "0".equals(a)) {
            return b;
        } else if (b == null || b.length() == 0 || "0".equals(b)) {
            return a;
        }

        //从低位向高位运算，也就是同时从后向前运算。结尾开始

        int max = Math.max(a.length(), b.length());
        int index = 0;
        char ii = '0';
        //+1是因为计算到最后，有可能进位
        char[] re = new char[max + 1];
        while (index < max) {
            //初始化a的值
            char aC = '0';
            //如果没超长就看当前位的值，超长了就用0计算
            if (index < a.length()) {
                aC = a.charAt(a.length() - 1 - index);
            }
            char bC = '0';
            //如果没超长就看当前位的值，超长了就用0计算
            if (index < b.length()) {
                bC = b.charAt(b.length() - 1 - index);
            }
            int count1 = 0;
            if (aC == '1') {
                count1++;
            }
            if (bC == '1') {
                count1++;
            }
            if (ii == '1') {
                count1++;
            }
            //当前有三个1
            if (count1 == 3) {
                //当前位
                re[re.length - 1 - index] = '1';
                //设置进位
                ii = '1';
                //两个1相加
            } else if (count1 == 2) {
                //当前位
                re[re.length - 1 - index] = '0';
                //设置进位
                ii = '1';
                //一个1
            } else if (count1 == 1) {
                //当前位
                re[re.length - 1 - index] = '1';
                //设置进位
                ii = '0';
            } else {
                //当前位
                re[re.length - 1 - index] = '0';
                //设置进位
                ii = '0';
            }
            //一个1相加
            index++;
        }

        //最后的进位判断
        if (ii == '1') {
            re[0] = '1';
            return String.valueOf(re);
        } else {
            return String.valueOf(re, 1, max);
        }
    }

}
